package _go

/*
面试题 08.01. 三步问题
难度
简单

67

收藏

分享
切换为英文
接收动态
反馈
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3
 输出：4
 说明: 有四种走法
示例2:

 输入：n = 5
 输出：13
提示:

n范围在[1, 1000000]之间*/
func waysToStep(n int) int {
	if n <= 0 {
		return 0
	}
	dp1, dp2, dp3 := 1, 2, 4
	if n == 1 {
		return dp1
	} else if n == 2 {
		return dp2
	} else if n == 3 {
		return dp3
	}
	for i := 4; i <= n; i++ {
		dp1, dp2, dp3 = dp2, dp3, (dp1+dp2+dp3)%1000000007
	}
	return dp3
}
